package leetcode.year2021.month11;

// 240. 搜索二维矩阵 II
public class _07_1SearchMatrix240 {
  //  然后考虑，如何优化，可以排除一些行, 限制m和n的查询范围

//   看到有序，就应该想到二分查找
  public boolean searchMatrix(int[][] matrix, int target) {
    // 基本的，先从每行二分查找开始
    int m = matrix.length;
    int n = matrix[0].length;
    // 限制m和n的查询范围
    for (int i = 0; i < m; i++) {
      if (binarySearch(matrix[i], target)){
        return true;
      }
    }
    return false;
  }

  private boolean binarySearch(int[] matrix, int target) {
    int length = matrix.length;
    int left = 0;
    int right = length - 1;
    while (left <= right){
      int mid = left + (right - left)/2;
      if (matrix[mid] == target) {
        return true;
      } else if (matrix[mid] > target){
        right = mid - 1;
      } else if (matrix[mid] < target){
        left = mid + 1;
      }
    }
    return false;
  }

  /**
   * 编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
   *
   * 每行的元素从左到右升序排列。
   * 每列的元素从上到下升序排列。
   *  
   *
   * 示例 1：
   *
   *
   * 输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
   * 输出：true
   * 示例 2：
   *
   *
   * 输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
   * 输出：false
   *  
   *
   * 提示：
   *
   * m == matrix.length
   * n == matrix[i].length
   * 1 <= n, m <= 300
   * -109 <= matrix[i][j] <= 109
   * 每行的所有元素从左到右升序排列
   * 每列的所有元素从上到下升序排列
   * -109 <= target <= 109
   *
   * 来源：力扣（LeetCode）
   * 链接：https://leetcode-cn.com/problems/search-a-2d-matrix-ii
   * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
   */
}
